package com.hr.剑指offer.work1;

/**
 * @author 周恒哲
 * @date 2020/06/16
 **/
public class 面试题22_链表中倒数第k个节点 {    /**
     * 双指针
     * 初始化： 前指针 former 、后指针 latter ，双指针都指向头节点 head​ 。
     * 构建双指针距离： 前指针 former 先向前走 kk 步（结束后，
     * 双指针 former 和 latter 间相距 kk 步）。
     * 双指针共同移动： 循环中，双指针 former 和 latter 每轮都向前走一步，
     * 直至 former 走过链表 尾节点 时跳出（跳出后， latter 与尾节点距离为 k-1，即 latter 指向倒数第 kk 个节点）。
     * 返回值： 返回 latter 即可。
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode first=head;
        ListNode last=head;
        for (int i = 0; i < k; i++) {
            first=first.next;
        }
        while (first!=null){
            first=first.next;
            last=last.next;
        }
        return last;
    }
}
